分治算法原理与实现——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）


  分治算法（Divide and Conquer），字面意思是 “分而治之”，是一种经典的算法思想。将一个规模庞大、难以直接解决的复杂原问题，按照一定的规则分解为若干个相互独立、结构与原问题相似但规模更小的子问题；递归或迭代地求解这些子问题；最后按照特定的策略将子问题的解合并起来，最终得到原问题的完整解。

拆分
8
4
5
7
1
3
6
2
拆分
8
4
5
7
拆分
1
3
6
2
拆分
8
4
拆分
5
7
拆分
1
3
拆分
6
2
治理
8
治理
4
治理
5
治理
7
治理
1
治理
3
治理
6
治理
2

教程目录导航

▼

一、算法原理

1.1 算法定义

分治算法的执行过程可概括为 “三步走”，这三步构成了分治的核心逻辑，缺一不可：

简单来说，分治算法就是 “把大问题拆成小问题解决，再把小问题的答案拼起来”，类似于 “拆解复杂任务，分工完成后汇总结果” 的工作模式。

1.2 关键特性

  1. 分治性：核心是 “分” 与 “合”，拆分是基础，合并是关键，缺少合并步骤则无法形成原问题的解；
  2. 自相似性：原问题与子问题具有相同的逻辑结构，这是能够递归求解子问题的前提；
  3. 独立性：分解后的子问题相互独立，不存在依赖关系，一个子问题的求解不会影响其他子问题的结果；
  4. 均衡性：最优的分治策略是将原问题分解为规模大致相当的子问题（通常是 2 个或多个等规模子问题），可有效降低时间复杂度；
  5. 递归性：多数分治算法通过递归实现 “治” 的步骤，少数场景下可通过迭代实现。

1.3 核心前提

分治算法有效执行的四个必要前提：

  1. 原问题规模较大，直接求解难度高、效率低；
  2. 原问题具有自相似性，可分解为结构相似的子问题；
  3. 子问题相互独立，求解过程互不干扰；
  4. 存在可行的合并策略，能够将子问题的解整合为原问题的解。

二、实现步骤

要实现一个高效的分治算法，通常遵循以下 4 个标准步骤：

步骤 1：定义问题与拆分规则（分）

明确原问题的求解目标，设计合理的拆分规则，将原问题分解为若干个规模均匀、结构相似的子问题。例如：

  1. 排序问题中，将数组从中间拆分为左右两个等规模子数组；查找问题中，将有序数组按中点拆分为左右两个子区间
  2. 百钱买百鸡的递推关系：
    • 固定x，逐步递增y进行试探，直到y超出范围；
    • y遍历完毕后，递增x，重新从y=0开始试探，形成递归分支；

步骤 2：设定基线条件（终止拆分）

明确子问题的最小规模边界，当子问题规模缩小到该边界（基线条件）时，无需再拆分，直接通过简单方法求解。例如：

  1. 排序问题中，当子数组长度为 1 时，本身就是有序的，直接返回；查找问题中，当子区间长度为 0 时，说明未找到目标元素。
  2. 百钱买百鸡的函数：void f(int x, int y)

步骤 3：递归求解子问题（治）

对每个拆分后的子问题，递归调用自身的求解逻辑，逐个得到子问题的解。这一步是分治算法的 “核心执行层”，依赖递归的自调用特性，逐步缩小问题规模。例如：

  1. 求质数的终止条件：
    • i × i > n（ 即i > sqrt(n) )，说明n无法被 2 到sqrt(n)的整数整除，是质数；
    • n % i == 0，说明n能被i整除，不是质数；
  2. 百钱买百鸡的终止条件：
    • 找到合法解：x+y+z=100 且 5x+3y+z/3=100，同时 z>=0、z是 3 的倍数；
    • 遍历完所有可能：x超过最大取值（14）或 y超过最大取值（25），停止当前分支递归；

步骤 4：设计合并策略（合）

根据原问题的需求，设计对应的合并规则，将所有子问题的解整合起来，形成原问题的最终解。这一步是分治算法的 “灵魂”，直接决定算法的效率和正确性。例如：

  1. 归并排序中的 “归并操作” 就是核心的合并逻辑
  2. 百钱买百鸡的终止条件：
    • 找到合法解：x+y+z=100 且 5x+3y+z/3=100，同时 z>=0、z是 3 的倍数；
    • 遍历完所有可能：x超过最大取值（14）或 y超过最大取值（25），停止当前分支递归；

三、优化思路

分治算法的优化核心围绕 “拆分效率” 和 “合并效率” 展开，同时规避潜在问题，常见优化方向有：

  1. 均衡拆分优化：尽量将原问题拆分为规模相当的子问题，避免出现 “一边大、一边小” 的失衡情况，可降低算法的时间复杂度（如将数组拆分为左右等长的子数组，而非极不均衡的比例）；
  2. 减少合并开销：合并步骤往往是分治算法的时间瓶颈，通过优化合并逻辑（如使用原地合并、减少数据拷贝），提升整体效率；
  3. 子问题转迭代：递归的栈开销可能超过分治的优势，此时可将子问题的求解转换为迭代（如插入排序），进一步优化性能；
  4. 避免重复计算：部分分治场景下可能存在重复子问题（如未优化的快速排序），通过缓存或调整拆分规则，避免重复求解相同子问题；
  5. 并行化优化：由于子问题相互独立，可利用多线程 / 多进程并行求解子问题，大幅提升大规模问题的处理效率（如并行归并排序）。

四、适用场景

分治算法适用于具有自相似性、子问题独立且可合并的大规模问题，常见包括：

  1. 排序问题（归并排序、快速排序，这是分治算法的经典应用）；
  2. 查找问题（二分查找、快速选择算法，用于有序数据的高效查找与 Top-K 求解）；
  3. 数值计算问题（大整数乘法、矩阵乘法（Strassen 算法）、傅里叶变换（FFT 算法））；
  4. 组合问题（分治求解子集、排列问题，大规模数据的组合筛选）；
  5. 树形结构与分治结合（二叉树的分治遍历、平衡二叉树的构建与查询）；
  6. 大规模数据处理（分布式系统中的数据分片处理，利用分治思想实现并行计算）。

五、代码示例

下面以 “归并排序” 为例，展示分治算法的实现。归并排序是分治算法的经典代表 —— 核心是 “分（拆分数组）+ 治（递归排序子数组）+ 合（合并有序子数组）”。

算法解析

  1. 分（拆分）：通过 mid = left + (right - left) / 2, 将数组拆分为 [left, mid] 和 [mid+1, right]，直到子数组长度为 1（递归终止）；
  2. 治（递归排序）：递归调用 mergeSort 分别排序左、右子数组，使子数组各自有序；
  3. 合（合并）：merge 函数是核心 —— 用两个指针遍历两个有序子数组，按大小依次放入临时数组，最后将临时数组的有序结果复制回原数组。

#include <iostream>
#include <iostream>
#include <vector>
using namespace std;

// 合并操作：将两个有序子数组[left, mid]和[mid+1, right]合并为一个有序数组
// arr：原数组
// temp：临时数组（用于存储合并结果，避免频繁创建数组）
// left：左子数组起始索引
// mid：拆分点（左子数组结束索引）
// right：右子数组结束索引
void merge(vector<int>& arr, vector<int>& temp, int left, int mid, int right) {
    // 1. 初始化指针
    int i = left;    // 左子数组指针
    int j = mid + 1; // 右子数组指针
    int k = left;    // 临时数组指针

    // 2. 合并两个有序子数组到临时数组
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 3. 处理左子数组剩余元素
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    // 4. 处理右子数组剩余元素
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 5. 将临时数组的有序结果复制回原数组
    for (int idx = left; idx <= right; idx++) {
        arr[idx] = temp[idx];
    }
}

// 分治实现归并排序（递归版）
// arr：待排序数组
// temp：临时数组（复用，减少内存开销）
// left：当前排序区间起始索引
// right：当前排序区间结束索引
void sort_recu(vector<int>& arr, vector<int>& temp, int left, int right) {
    // 递归终止条件：区间只有1个元素或空（天然有序）
    if (left >= right) {
        return;
    }

    // 1. 分：计算中间点，拆分为左、右子数组
    int mid = left + (right - left) / 2; // 避免(left+right)溢出

    // 2. 治：递归排序左、右子数组
    sort_recu(arr, temp, left, mid);    // 排序左区间[left, mid]
    sort_recu(arr, temp, mid + 1, right); // 排序右区间[mid+1, right]

    // 3. 合：合并两个有序子数组
    merge(arr, temp, left, mid, right);
}

// 包装函数：简化调用（无需手动传入temp、left、right）
void sort_recu(vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return; // 空数组或单元素数组无需排序
    }
    vector<int> temp(arr.size()); // 创建临时数组（仅创建一次，复用）
    sort_recu(arr, temp, 0, arr.size() - 1);
}

// 迭代版归并排序
void sort_iter(vector<int>& arr) {
    int n = arr.size();
    vector<int> temp(arr.size()); // 创建临时数组（仅创建一次，复用）
    // 子数组大小从1开始，每次翻倍
    for (int current_size = 1; current_size < n; current_size *= 2) {
        // 遍历数组，合并相邻的两个子数组
        for (int left = 0; left < n - 1; left += 2 * current_size) {
            // 计算左子数组的结束位置
            int mid = std::min(left + current_size - 1, n - 1);
            // 计算右子数组的结束位置
            int right = std::min(left + 2 * current_size - 1, n - 1);
            // 合并两个子数组
            merge(arr, temp, left, mid, right);
        }
    }
}

// 辅助函数：打印数组
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    // 测试数组
    vector<int> arr1 = {8, 4, 5, 7, 1, 3, 6, 2};
    vector<int> arr2 = {8, 4, 5, 7, 1, 3, 6, 2};
    cout << "排序前数组：";
    printArray(arr1);
    cout << "排序前数组：";
    printArray(arr2);

    // 归并排序(迭代)
    sort_iter(arr1);

    // 归并排序(递归)
    sort_recu(arr2);

    cout << "迭代排序后数组：";
    printArray(arr1);

    cout << "递归排序后数组：";
    printArray(arr2);

    return 0;
}

输出结果


排序前数组：8 4 5 7 1 3 6 2
排序前数组：8 4 5 7 1 3 6 2
迭代排序后数组：1 2 3 4 5 6 7 8
递归排序后数组：1 2 3 4 5 6 7 8

六、优缺点

优点

  1. 高效性：通过拆分问题降低时间复杂度，多数分治算法的时间复杂度为 O (n log n)（如归并排序、快速排序），远优于暴力枚举的 O (n²)；
  2. 扩展性强：子问题独立的特性使其天然支持并行计算，可在分布式系统中大规模推广；
  3. 逻辑清晰：将复杂问题拆解为简单子问题，代码结构清晰，可读性强，便于维护；
  4. 适用范围广：可解决排序、查找、数值计算等多种大规模问题，灵活性高。

缺点

  1. 空间开销：部分分治算法（如归并排序）需要额外的辅助空间存储合并过程中的数据，空间复杂度较高（归并排序的空间复杂度为 O (n)）；
  2. 递归依赖：多数分治算法依赖递归实现，递归深度过大时可能出现栈溢出风险；
  3. 不适用于子问题依赖的场景：当子问题存在相互依赖时，无法使用分治算法求解。

七、算法对比

对比维度 分治算法 枚举算法
核心思想 分而治之（分 + 治 + 合） 穷举解空间（遍历 + 验证）
依赖关 可依赖递归（或迭代）实现 依赖循环遍历
子问题特性 子问题独立、结构相似 无明确子问题，仅候选解
关键步骤 合并子解（核心） 验证条件（核心）
时间复杂度 常较低（O (n log n)） 通常较高（O (n²) 及以上）
空间复杂度 可能需要额外辅助空间 通常较低（无需额外空间）

八、总结

  1. 分治算法的核心是 分（拆分）、治（求解）、合（合并）三步，依赖问题的自相似性和子问题独立性；
  2. 实现关键是 “均衡拆分、明确基线条件、高效合并”，优化核心是降低拆分与合并的开销；
  3. 经典应用包括归并排序、快速排序、二分查找等，适用于大规模、可拆分、子问题独立的场景；
  4. 优势是高效、可并行、逻辑清晰，劣势是存在空间开销和递归栈溢出风险；
  5. 与递归、枚举相比，分治算法更适合解决复杂大规模问题，是算法设计中的核心思想之一。

返回顶部